⟸ pàgina anterior ⟸

Exercici 10 (Tasca 2).

(regular languages, decidable properties)

DFAs – propietats decidibles

Demostreu que els problemes computacionals següents són decidibles proporcionant un algorisme (de cost raonable) que els resol.

1. Donat un DFA A, és L(A)=\emptyset?
2. Donat un DFA A, és L(A) un conjunt infinit?
3. Donats dos DFAs A i B, és L(A)=L(B)?
4. Donats dos DFAs A i B, és L(A)\subseteq L(B)?